/**
 * 
 */
package edu.cornell.cs.lsi.mapreduce.pass2;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

/**
 * This class implements the Union Find algorithm.
 * @author poornima
 *
 */
public class UnionFindImpl {
	
	/**
	 * Data structure the maintain the graph components. 
	 */
	private Hashtable<Point, Point> compTable;
	
	int connectedComps;
	
	/**
	 * Default constructor.
	 */
	public UnionFindImpl(){
		compTable = new Hashtable<Point, Point>();
	}
	
	/**
	 * Finds the union of two vertices.
	 * @param v1 vertex 1 
	 * @param v2 vertex 2
	 */
	private void union(Point v1,Point v2){
		// p1HierarchyLvl, keeps track of the hierarchy for the point v1, useful for path compression
		List<Point> p1HierarchyLvl = new ArrayList<Point>();
		// p2HierarchyLvl, keeps track of the hierarchy for the point v2, useful for path compression
		List<Point> p2HierarchyLvl = new ArrayList<Point>();
		// find the root vertex for v1
		Point v1Val = find(v1,p1HierarchyLvl);
		// find the root vertex for v2
		Point v2Val = find(v2,p2HierarchyLvl);
		if(v1Val.equals(v2Val)){
			// the roots are equal, so the components are connected.
			return;
		}
		// compute which point is at south-west corner
		if(v1Val.getX() < v2.getX()){
			// v1 is at south-west corner
			compTable.put(v2, v1Val);
			// compresses the path for all the other vertices that have v1 as root vertex.
			// all the other vertices will now point v1Val as root.
			compressPath(v1Val, p2HierarchyLvl);
		}else if(v1Val.getX() > v2.getX()){
			compTable.put(v1, v2Val);
			compressPath(v2Val, p1HierarchyLvl);
		}else if(v1Val.getY() < v2Val.getY()){
			compTable.put(v2, v1Val);
			compressPath(v1Val, p2HierarchyLvl);
		}else if(v1Val.getY() > v2Val.getY()){
			compTable.put(v1, v2Val);
			compressPath(v2Val, p1HierarchyLvl);
		}		
	}
	
	/**
	 * This method will compress path for all the points pointed out in the <tt>hierarchyLvls</tt>.
	 * All the points in the <tt>hierarchyLvls</tt> will now point to <tt>root</tt> as their root vertex.
	 * <p> 
	 * @param root The root vertex
	 * @param hierarchyLvls List of points whose paths have to be compressed
	 */
	private void compressPath(Point root,List<Point> hierarchyLvls){
		if(root == null || hierarchyLvls == null || hierarchyLvls.isEmpty()){
			return;			
		}
		for(Point pt : hierarchyLvls){
			compTable.put(pt, root);
		}		
	}
	
	/**
	 * Finds the parent of vertex v1, records the hierarchy level in <tt>level</tt>
	 * @param v1 vertex v1
	 * @param level hierarchy level
	 * @return the parent of v1
	 */
	private Point find(Point v1,List<Point> hierarchyLevels){
		if(!compTable.containsKey(v1)){
			//Point pt = new Point(v1,v1);
			compTable.put(v1, v1);
			//++connectedComps;
			return v1;
		}
		Point result = v1;
		while(compTable.get(result) != result){
			result = compTable.get(result);
			if(hierarchyLevels != null){
				hierarchyLevels.add(result);
			}			
		}
		return result;
	}
	
	/**
	 * This method returns <true> if <tt>v1</tt> is connected to <tt>v2</tt>.
	 * @param v1 vertex v1
	 * @param v2 vertex v2
	 * @return <true> if v1 is connected to v2
	 */
	private boolean isConnected(Point v1,Point v2){
			return find(v1,null).equals(find(v2,null));
	}

	/**
	 * This method will do a union find for the given two vertices.
	 * @param v1 vertex 1
	 * @param v2 vertex 2
	 */
	public void doUnionFind(Point v1, Point v2){
		if(isConnected(v1, v2)){
			return;
		}
		union(v1,v2);		
	}
	
	/**
	 * Returns the root vertex for the point <tt>pt</tt>.
	 * @param pt The point for which the root vertex has to be returned. 
	 * @return The  root vertex
	 */
	public Point getRoot(Point pt){
		if(pt == null){
			return null;
		}
		return compTable.get(pt);		
	}
	
	public void addEdge(Point vertex, Point rootVertex){
		if(vertex == null || rootVertex == null){
			System.out.println("ERROR: error while adding the edge.");
			return;
		}
		compTable.put(vertex, rootVertex);
	}
	
	public Hashtable<Point, Point> getComponentTable(){
		return compTable;
	}
	
	/**
	 * Displays the map, used for debugging purposes. 
	 */
	public void displayMap(){
		if(compTable == null || compTable.isEmpty()){
			System.out.println("WARN: the data structure is empty.");
			return;
		}
		StringBuffer display;
		for(Map.Entry<Point,Point> entry : compTable.entrySet()){
			display = new StringBuffer("");
			display.append("------ KEY:(");
			display.append(entry.getKey().getX());
			display.append(",");
			display.append(entry.getKey().getY());
			display.append(")");
			display.append("------ ROOT:(");
			display.append(entry.getValue().getX());
			display.append(",");
			display.append(entry.getValue().getY());
			display.append(")");
			System.out.println(display.toString());
		}
		
	}
	
	private static void  test01(){
		UnionFindImpl main = new UnionFindImpl();
		//main.connectedComps = srcVtx.length;
        System.out.println("-------- pass 1 ----------");
        main.doUnionFind(new Point(0.1393873f,0.274788f), new Point(0.08483798f,0.3433955f));
        main.displayMap();
      //  main.doUnionFind(new Point(0,2), new Point(3,3));
        System.out.println("-------- pass 2 ----------");
        //main.displayMap();
       // main.doUnionFind(new Point(1,4), new Point(3,3));
        System.out.println("-------- pass 3 ----------");
        //main.displayMap();
       // main.doUnionFind(new Point(1,1), new Point(2,2));
        System.out.println("-------- pass 4 ----------");
        //main.displayMap();
      //  main.doUnionFind(new Point(2,2), new Point(2,0));
        System.out.println("-------- pass 5 ----------");
        //main.displayMap();
      //  main.doUnionFind(new Point(2,0), new Point(1,1));
        System.out.println("-------- pass 6 ----------");
        //main.displayMap();
	}
	
	/**
	 * Main method for testing/debugging.
	 */
	public static void main(String args[]){
		test01();
	}
}
